/**
 * 弗洛伊德(Floyd)算法:图里每个顶点到多个源顶点的最短距离的动态规划算法
 * @param graph 图
 * 采用一个中间点，如果开始点到中间点的距离加上中间点到结束点的距离，要小于
 * 开始点到结束点的距离，就将更新“开始点到结束点的距离”的值为那个小的值
 */
export const floydWarshall = (graph: number[][]) => {
    const dist: number[][] = [];
    const length = graph.length;
    // 初始化距离
    for (let i = 0; i < length; i ++) {
        dist[i] = [];
        for (let j = 0; j < length; j ++) {
            // 自己本身距离就是0
            if (i === j) {
                dist[i][j] = 0;
            } else if (!isFinite(graph[i][j])) {
                // 不相邻，距离就是无穷大
                dist[i][j] = Infinity;
            } else {
                dist[i][j] = graph[i][j];
            }
        }
    }

    // k是中间点
    for (let k = 0; k < length; k ++) {
        // i是开始点
        for (let i = 0; i < length; i ++) {
            // j是结束点
            for (let j = 0; j < length; j ++) {
                // 如果开始点到中间点的距离加上中间点到结束点的距离，要小于
                // 开始点到结束点的距离，就将更新
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    return dist;
};
